
看下23.2节中介绍的Sqrt<>模板，主模板是一般的递归计算，使用模板参数N(用于计算平方根的值)和其他两个可选参数调用。这些可选参数表示结果可以拥有的最小值和最大值。若模板只调用一个参数，并且我们已知平方根至少是1，所以结果最多是值本身。

然后递归使用二分搜索技术(通常称为二分法)。模板内部，计算值是在LO和HI之间的范围的前半部分，还是后半部分，这种情况使用三元操作符来区分。若二分的中间值大于N，我们继续上半部分的搜索。若二分的中间值小于等于N，对第二部分使用相同的模板。当LO和HI具有相同的值M(即最终值)时，偏特化结束递归。

模板实例化并不简单:即使是相对普通的类模板，也可以为每个实例分配超过1千字节的存储空间，并且在编译完成之前不能回收这些存储空间。因此，可以来研究一下使用Sqrt模板的编程细节:

\hspace*{\fill} \\ %插入空行
\noindent
\textit{meta/sqrt1.cpp}
\begin{lstlisting}[style=styleCXX]
#include <iostream>
#include "sqrt1.hpp"

int main()
{
	std::cout << "Sqrt<16>::value = " << Sqrt<16>::value << ’\n’;
	std::cout << "Sqrt<25>::value = " << Sqrt<25>::value << ’\n’;
	std::cout << "Sqrt<42>::value = " << Sqrt<42>::value << ’\n’;
	std::cout << "Sqrt<1>::value = " << Sqrt<1>::value << ’\n’;
}
\end{lstlisting}

表达式

\begin{lstlisting}[style=styleCXX]
Sqrt<16>::value
\end{lstlisting}

可扩展为

\begin{lstlisting}[style=styleCXX]
Sqrt<16,1,16>::value
\end{lstlisting}

模板内部，元程序计算Sqrt<16,1,16>::value:

\begin{lstlisting}[style=styleCXX]
mid = (1+16+1)/2
	= 9
value = (16<9*9) ? Sqrt<16,1,8>::value
				: Sqrt<16,9,16>::value
	  = (16<81) ? Sqrt<16,1,8>::value
				: Sqrt<16,9,16>::value
	  = Sqrt<16,1,8>::value
\end{lstlisting}

计算结果为Sqrt<16,1,8>::value，展开如下:

\begin{lstlisting}[style=styleCXX]
mid = (1+8+1)/2
	= 5
value = (16<5*5) ? Sqrt<16,1,4>::value
				: Sqrt<16,5,8>::value
	  = (16<25) ? Sqrt<16,1,4>::value
				: Sqrt<16,5,8>::value
	  = Sqrt<16,1,4>::value
\end{lstlisting}

Sqrt<16,1,4>::value分解如下:

\begin{lstlisting}[style=styleCXX]
mid = (1+4+1)/2
	= 3
value = (16<3*3) ? Sqrt<16,1,2>::value
				: Sqrt<16,3,4>::value
	  = (16<9) ? Sqrt<16,1,2>::value
				: Sqrt<16,3,4>::value
	  = Sqrt<16,3,4>::value
\end{lstlisting}

最后，Sqrt<16,3,4>::value的结果如下:

\begin{lstlisting}[style=styleCXX]
mid = (3+4+1)/2
	= 4
value = (16<4*4) ? Sqrt<16,3,3>::value
				: Sqrt<16,4,4>::value
	  = (16<16) ? Sqrt<16,3,3>::value
				: Sqrt<16,4,4>::value
	  = Sqrt<16,4,4>::value
\end{lstlisting}

因为匹配捕获相等的上下界的显式特化，所以Sqrt<16,4,4>::value结束递归进程。最终的结果是

\begin{lstlisting}[style=styleCXX]
value = 4
\end{lstlisting}

\subsubsubsection{23.3.1\hspace{0.2cm}跟踪所有实例化}

上面的分析计算16的平方根，当编译器计算表达式时

\begin{lstlisting}[style=styleCXX]
(16<=8*8) ? Sqrt<16,1,8>::value
		  : Sqrt<16,9,16>::value
\end{lstlisting}

不仅实例化正分支中的模板，还实例化负分支中的模板(Sqrt<16,9,16>)。此外，由于代码试图使用::操作符访问结果类类型的成员，该类类型内的所有成员也会实例化。这意味着Sqrt<16,9,16>的完全实例化会导致Sqrt<16,9,12>和Sqrt<16,13,16>的完全实例化。当详细检查整个过程时，会发现生成了几十个实例，总数是N值的两倍。

有一些技术可以减少实例化数量的激增。为了介绍这样的技术，这里重写Sqrt元程序:

\hspace*{\fill} \\ %插入空行
\noindent
\textit{meta/sqrt2.hpp}
\begin{lstlisting}[style=styleCXX]
#include "ifthenelse.hpp"

// primary template for main recursive step
template<int N, int LO=1, int HI=N>
struct Sqrt {
	// compute the midpoint, rounded up
	static constexpr auto mid = (LO+HI+1)/2;
	
	// search a not too large value in a halved interval
	using SubT = IfThenElse<(N<mid*mid),
	Sqrt<N,LO,mid-1>,
	Sqrt<N,mid,HI>>;
	static constexpr auto value = SubT::value;
};

// partial specialization for end of recursion criterion
template<int N, int S>
struct Sqrt<N, S, S> {
	static constexpr auto value = S;
};
\end{lstlisting}

关键变化是IfThenElse模板的使用，该模板19.7.1节中介绍过。IfThenElse模板是一个基于给定布尔常数，在两种类型之间进行选择的工具。若该常量为真，则第一个类型被类型别名为type;否则，Type代表第二种类型。并且，为类模板实例定义类型别名，不会导致C++编译器实例化该实例体。因此，当代码如下时

\begin{lstlisting}[style=styleCXX]
using SubT = IfThenElse<(N<mid*mid),
						Sqrt<N,LO,mid-1>,
						Sqrt<N,mid,HI>>;
\end{lstlisting}

Sqrt<N,LO,mid-1>和Sqrt<N,mid,HI>都没有完全实例化。查找SubT::value时，这两种类型中的一种最终成为SubT的同义词会进行完全实例化。与我们的第一种方法相反，这种策略导致了与log2(N)成比例的大量实例化:当N变得相当大时，元编程的成本降低了。















